import sys,os

#Merge sort
def mergesort(ay):
    ln = len(ay)
    while ln > 2:
        s = int(ln/2)
        return _merge(mergesort(ay[:s]),mergesort(ay[s:]))
    if ln == 2:
        return ay[0] < ay[1] and ay or [ay[1],ay[0]]
    return ay

#Merge 2 arrays,insert arrayb into arraya
def _merge(a,b):
    #make sure that b is 'lower' than a
    if b[0] > a [0]:a,b = b,a
    offset = 0
    for i in range(0,len(b)):
       while b[i] >= a[offset]:
           offset = offset + 1
           if offset >= len(a):break
       a.insert(offset,b[i])
    return a

s = [44,4,33,56,12,223,1,12,3,7,3,4,11,58,99,33]
b = s[:]
b.sort()
print b
print  mergesort(s)


